package list;

public class 两两交换链表中的节点_21 {
    //递归解法
    public ListNode_ swapPairs(ListNode_ head) {
        if (head == null || head.next == null) return head;
        ListNode_ nextnext = swapPairs(head.next.next);
        ListNode_ newHead = head.next;
        newHead.next = head;
        head.next = nextnext;
        return newHead;
    }

    //迭代解法最好用一个虚拟头节点 这是一个小技巧
    public ListNode_ swapPairs_(ListNode_ head) {
        if (head == null || head.next == null) return head;
        // 要保存每组节点的前驱指针  需要一个伪节点  并后移伪节点
        ListNode_ dummyHead = new ListNode_(0, head), cur = dummyHead;
        while (cur.next != null && cur.next.next != null) {
            // 这里有三个几点在操作中  cur.next  node1 node2
            ListNode_ node1 = cur.next.next;
            ListNode_ node2 = cur.next.next.next;
            node1.next = cur.next;   // 第二个节点指向第一个节点
            cur.next.next = node2;   // 第一个节点指向后面的节点
            cur.next = node1;        // 当前指针指向第一个节点
            cur = node1.next;        // 指针后移到后一组节点的前驱节点
        }
        return dummyHead.next;
    }

}

class ListNode_ {
    int val;
    ListNode_ next;

    ListNode_() {
    }

    ListNode_(int val) {
        this.val = val;
    }

    ListNode_(int val, ListNode_ next) {
        this.val = val;
        this.next = next;
    }
}